package com.kongge.algorithm.demo;

/**
 * 
 * @author kongge
 * 1  2  8  9
 * 2  4  9  12
 * 4  7  10 13
 * 6  8  11 15
 * 在二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 */
public class TwoDimensionalArrayContainsNumber implements IAlgorithm{
	
	public void execute() {
		int[][] arr = {{1, 2, 8,  9},
					   {2, 4, 9,  12},
					   {4, 7, 10, 13}, 
					   {6, 8, 11, 15}};
		int number = 7;
		boolean isFind = findInArr(arr, number);
		System.out.println("The result is " + isFind);
	}
	
	/**
	 * 从右上角还是查找，如果第一个就大于number，则这一列就可忽略，继续往左边查找
	 * 如果该数字小于number，则这一行忽略，继续向下查找
	 * @param arr
	 * @param number
	 * @return
	 */
	private boolean findInArr(int[][] arr, int number) {
		if (arr == null) {
			return false;
		}
		int row = arr.length;
		int col = arr[0].length;
		for (int j = col - 1; j >= 0; j--) {
			for (int i = 0; i < row; i++) {
				if (arr[i][j] > number) {
					break;
				} else if (arr[i][j] == number) {
					return true;
				}
			}
		}
		return false;
	}

}
